package xyz.robinbingo.leetcode.a20.b05.c24;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        List<Integer> l1 = Arrays.stream(nums1).boxed().collect(Collectors.toList());
        List<Integer> l2 = Arrays.stream(nums2).boxed().collect(Collectors.toList());
        return (getk(l1, l2, left) + getk(l1, l2, right)) / 2.0;
    }

    private double getk(List<Integer> l1, List<Integer> l2, int k) {
        if (l1.size() > l2.size()) {
            return getk(l2, l1, k);
        }
        if (l1.isEmpty()) {
            return l2.get(k - 1);
        }
        if (k == 1) {
            return Math.min(l1.get(0), l2.get(0));
        }
        int min = Math.min(k / 2, l1.size());
        if (l1.get(min - 1) < l2.get(min - 1)) {
            return getk(l1.subList(min, l1.size()), l2, k - min);
        } else {
            return getk(l1, l2.subList(min, l2.size()), k - min);
        }
    }
}